# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
x=3
# head=ListNode(1,None)
# head.next=ListNode(1,None)
head=ListNode(1,None)
head.next=ListNode(2,None)
head.next.next=ListNode(3,None)
head.next.next.next=ListNode(0,None)
head.next.next.next.next=ListNode(2,None)
head.next.next.next.next.next=ListNode(5,None)
# head.next.next.next.next.next.next=ListNode(2,None)
def partition(head, x):
    if head==None or (head!=None and head.next==None):
        return head
    flag=False
    #定位到第一个大于等于x的位置，以及其前一个位置
    # 先判断头结点
    if head.val>=x:
        #如果是头结点就是大于等于x的，就在头结点处进行插入
        num=0
        theInsertBeforeLoc=None
        flag=True
    else:
        #如果头结点不是
        num=1
        process=head.next
        theInsertBeforeLoc=head
        while process!=None:
            if process.val>=x:
                #找到插入位置了，相当于
                flag=True
                break
            #暂未找到插入位置
            theInsertBeforeLoc = process
            process=process.next
            num+=1
    if flag:
        process=head
        processNext=head.next
        index=1
        while process!=None and processNext!=None:
            if index>num and processNext.val<x:
                #要被处理
                #从现有位置删除掉当前的结点
                process.next=processNext.next
                #把当前结点插入到前面的位置中
                if theInsertBeforeLoc==None:
                    #在头结点处插入
                    print("在头部插入")
                    processNext.next=head
                    theInsertBeforeLoc=processNext
                    head=theInsertBeforeLoc
                else:
                    processNext.next=theInsertBeforeLoc.next
                    theInsertBeforeLoc.next=processNext
                    theInsertBeforeLoc=processNext
                processNext=process.next
            else:
                # 不被处理的情况
                process=process.next
                processNext=processNext.next
            index+=1
    else:
        pass
    process=head
    while process!=None:
        print(process.val)
        process=process.next

partition(head,x)
